import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Solve {

    private int[] quickSort(int[] array, int left, int right) {

        if(left > right) {
            return array;
        }

        int i = left;
        int j = right;
        int pos = array[left];
        while(i < j) {
            //从右往左,找到第一个比基准值小的
            while (i < j && array[j] >= pos) {
                j --;
            }
            //从左往右，找到第一个比基准值大的
            while (i < j && array[i] <= pos) {
                i++;
            }

            //交换找到的两个元素
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // i == j的时候，就是pos应该去的位置,交换他们两个
        if(i == j) {
            array[left] = array[i];
            array[i] = pos;
        }


        quickSort(array, left, i-1);
        quickSort(array, j+1, right);
        return array;

    }

    /**
     * 二分查找
     * @param array
     * @param low
     * @param high
     * @param aim
     * @return
     */
    private int binSearch(int [] array, int low, int high, int aim) {
        int middle = (low + high) / 2;

        if(array[middle] == aim) {
            return middle;
        } else if(array[middle] > aim ) {
            return binSearch(array, low, middle-1, aim);
        } else if(array[middle] < aim ) {
            return binSearch(array, middle + 1, high, aim);
        } else {
            return -1;
        }
    }

    /**
     * 最长无重复子串
     */
    private String longestNoRepeatString(String str) {
        List<Character> list = new ArrayList<>();
        String result = "";
        for(int i=0; i<str.length(); i++) {
            if(!list.contains(str.charAt(i))) {
                list.add(str.charAt(i));
            } else {
                if(result.length() < listToString(list).length()) {
                    result = listToString(list);
                }
                while (!list.isEmpty() && list.contains(str.charAt(i))) {
                    list.remove(0);
                }
                list.add(str.charAt(i));
            }

        }
        return result = result.length() > listToString(list).length() ? result : listToString(list);
    }

    private String listToString(List<Character> list) {
        String str = list.stream().map(item->{
            return String.valueOf(item);
        }).reduce((a,b) -> {return a + b;}).orElseGet(()->"");

        return str;
    }

    /**
     * 树的深度遍历 用堆栈
     * @param args
     */
//    private dtraverse(Node root) {
//        Stack<Node> stack = new Stack();
//        while (root!= null &&!stack.isEmpty()) {
//            while (root != null) {
//                stack.push(root);
//                root = root.leftChild;
//            }
//            if(!stack.isEmpty()) {
//               Node node = stack.pop();
//               System.out.println(node.data);
//               root = node.rightChild;
//            }
//        }
//    }

    /**
     * 树的广度遍历，队列
     * @param args
     */
//    private traverse(Node node) {
//        Queue queue = new ArrayDeque();
//        queue.push(node);
//        while (!queue.isEmpty()){
//            Node node = queue.pop();
//            if(node == null) {
//                continue;
//            }
//            System.out.println(node.data);
//            if(node.leftChild != null) {
//                queue.push(node.leftChild);
//            }
//            if(node.rightChild != null) {
//                queue.push(node.rightChild);
//            }
//        }
//    }

    /**
     * 整数翻转
     */
    private int reverse(int n) {
        int reverseNum = 0;
        while(n !=0) {
            if(reverseNum > Integer.MAX_VALUE/10  || reverseNum < Integer.MIN_VALUE / 10) {
                return 0;
            }
            int yushu = n %10;
            n = n / 10;
            reverseNum = reverseNum * 10 + yushu;
        }
        return reverseNum;
    }


    private String findTheMostOccurrence(String []array) {
        Map<String, Long> map = Arrays.stream(array).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        TreeMap<Long, String> treeMap = new TreeMap<>();
        for(Map.Entry<String, Long> entry : map.entrySet()) {
            if(treeMap.get(entry.getValue()) == null) {
                treeMap.put(entry.getValue(), entry.getKey());
            } else {
                String str = treeMap.get(entry.getValue());
                str = str + "-" + entry.getKey();
                treeMap.put(entry.getValue(), str);
            }
        }

        treeMap.entrySet().stream().forEach(entry->{
            System.out.println(entry.getKey() + " " + entry.getValue());
        });

        return null;
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        for (String word : words) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
                return entry1.getValue().equals(entry2.getValue()) ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();
            }
        });
        for (Map.Entry<String, Integer> entry : cnt.entrySet()) {

            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> ret = new ArrayList<String>();
        while (!pq.isEmpty()) {
            ret.add(pq.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String []args) {
//        int []array = new int[]{1,2,6,4,1,9,2,5,8,10};
//        Arrays.stream(new Solve().quickSort(array, 0, array.length-1)).forEach(item->{System.out.print(item + " ");});
//        System.out.println();
//        int []sortArray = new int[]{1,2,3,4,5,6,7,8,9,10};
//        System.out.println(new Solve().binSearch(sortArray, 0, array.length-1, 5));
//        System.out.println(new Solve().longestNoRepeatString("abcabcde"));
//        System.out.println(new Solve().reverse(123));



        String []strArray = new String[]{"a","b","a","c"};
        new Solve().findTheMostOccurrence(strArray);

        Integer v1 = 128;
        Integer v2 = 128;
        System.out.println(v1 == v2);
        System.out.println(v1.equals(v2));
    }
}
